#
# @lc app=leetcode.cn id=34 lang=python3
#
# [34] 在排序数组中查找元素的第一个和最后一个位置
#

# @lc code=start
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def getRightBorder(nums: List[int], target: int) -> int:
            left, right = 0, len(nums) - 1
            rightBorder = -2
            while left <= right:
                mid = int(left + (right - left) / 2)
                if  nums[mid] > target:
                    right = mid - 1
                else:
                    left = mid + 1
                    rightBorder = left
            
            return rightBorder
        
        def getLeftBorder(nums: List[int], target: int) -> int:
            left, right = 0, len(nums) - 1
            leftBorder = -2
            while left <= right:
                mid = int(left + (right - left) / 2)
                if  nums[mid] < target:
                    left = mid + 1
                else:                   
                    right = mid - 1
                    leftBorder = right
            
            return leftBorder
        
        leftBorder = getLeftBorder(nums, target)
        rightBorder = getRightBorder(nums, target)

        if leftBorder == -2 or rightBorder == -2: return[-1, -1]
        if rightBorder - leftBorder > 1: return[leftBorder+1, rightBorder-1]
        return[-1, -1]



# @lc code=end

